A universal hash function is a function for converting input of a predetermined input space into output of a fixed length. Unlike cryptographic hash functions such as SHA-1 (Secure Hash Algorithm 1) and MD5 (Message Digest 5), a random key is also used as an input. A universal hash function H using an input x and a key k is formally expressed by Expression 1 shown below.y=H(k,x)   (Expression 1)
Where a key space is D_key, a set of functions {H(k,*): k in D_key} is sometimes called a family of universal hash functions.
The concept of universal hash functions was initially proposed by Carter and Wegman and since then have been used as an elemental technique in various fields of cryptographic technology. Typical examples thereof include a system such as HMAC (Keyed-Hashing for Message Authentication Code) using a cryptographic hash function in the field of Message Authentication Code (MAC) as well as a method that combines a universal hash function and a block cipher or a stream cipher. This method is called Carter-Wegman MAC (CW-MAC). In some constructions of universal hash functions, Carter-Wegman MAC is known to be capable of significantly fast computation.
There are some variations of properties required for universal hash functions. A typical property is a property called e-almost universal. When the relation of Expression 2 shown below is satisfied for an input space D_in, an output space D_out, and a key space D_key, the function H: D_key×D_in->D_out is said to be an (e-AU) hash function that satisfies the property of e-almost universal.Pr_K[H(K,x)=H(K,x′)]≦e, for all x≠x′, x,x′ in D_in   (Expression 2)
That is, Expression 2 shown above indicates the probability that the outputs of H agree for two different inputs is merely e when the key is a uniform random number over D_key. When a keyed function H satisfies Expression 2 shown above, H is said to be an e-AU hash function.
When D_out is an n-bit space and satisfies the relation of Expression 3 shown below, H is said to be an (e-AXU) hash function that satisfies the property of e-almost XOR universal.Pr_K[H(K,x) xor H(K,x′)=d]≦e, for all x≠x′, x,x′ in D_in, for all d in D_out   (Expression 3)
In Expression 3 shown above, x xor y denotes the exclusive OR (XOR) of x and y for each bit. When input and output spaces are the same, e-AXU is a stronger condition than e-AU. When a keyed function H satisfies Expression 3 shown above in the same manner as the e-AU hash function, H is said to be an e-AXU hash function.
Here, an e-AU hash function with two block inputs and one block output or an e-AXU function with one block input/output will be mainly described as the most basic form of universal hash functions. The block length is n bits, unless otherwise specified. If H(k,x) is an e-AXU hash function with one block input/output, a function G with two block inputs and one block output shown by Expression 4 below is always an e-AU hash function.G(k,(x[1],x[2]))=H(k,x[1]) xor x[2]  (Expression 4)
It is known that data of arbitrary length can be processed by processing data like a binary tree using the e-AU hash function with two block inputs and one block output (see, for example, NPL 1). Therefore, if the e-AXU hash function with one block input/output is designed, universal hash functions of every length can be generated in principle.
There are many researches for specific methods for creating e-AU or e-AXU universal hash functions. One of the most popular methods is a method using a finite field GF(2n). This method defines a function H by Expression 5 shown below, for example, when the input space is GF(2n) and the output space is GF(2n).H(K,x[1])=x[1]mult K   (Expression 5)
In Expression 5, K denotes a uniform random number over GF(2n), and mult denotes multiplication over GF(2n). GF(2n) has 2n elements and thus can be uniquely expressed by an n-bit sequence. Therefore, H in Expression 5 shown above is a keyed function with n-bit input/output and is known to be (1/2n)-AXU. This value is the theoretical minimum value in the case of an n-bit output. For the same reason as the reason shown for Expression 4, it is understood that H in Expression 6 shown below is a keyed function with a 2n-bit input and an n-bit output, and is (1/2n)-AU.H(K,(x[1],x[2]))=x[1]mult K+x[2]  (Expression 6)
In Expression 6 shown above, +denotes addition (that is, xor) over GF(2n). Except for this, the expression is the same as Expression 5.
NPL 2 describes a method using a Toeplitz matrix proposed by Krawczyk. When the i-th row j-th column component in a binary Toeplitz matrix of n rows and m columns is written as c(i,j) in {0,1}, c(i,j) satisfies the relation of Expression 7 shown below.c(i,j)=c(i+1,j+1) for any 1≦i≦n−1, any 1≦j≦m−1   (Expression 7)
That is, all the components on a diagonal are the same, and the matrix can be uniquely determined by designating n+m−1 components included in the first column and the first row. According to NPL 2, in a binary Toeplitz matrix M of n rows and m columns, when the n+m−1 independent components are given at random each from the range {0,1}, the (1/2n)-AXU hash function can be constructed using an m-bit input and an n-bit output by a matrix product. That is, this function is defined by Expression 8 shown below.ToplitzHash(K,x)=M·x   (Expression 8)
In Expression 8, x denotes m bits, K denotes a (n+m−1)-bit key, and M denotes a random, binary Toeplitz matrix of n rows and m columns in which the first column and the first row are set using K. M·x denotes a matrix-vector product, and the result is n bits. The bitwise computation is performed as a Boolean variable. Specifically, when a binary square Toeplitz matrix of n rows and n columns is used, the key is 2n−1 bits.
NPL 2 further describes a method in which, considering the case where m is far greater than n, the first column and the first row are set as an output sequence of a Linear Feedback Shift Register (LFSR) the initial value of which is set at random. By using this method, the length of the key can be set as a constant that is not directly relevant to the size of the matrix.
There are some applied methods of the e-AXU hash function with n-bit input/output. This hash function is applied in encryption and authentication in combination with block ciphers. For example, an extended block cipher called Tweakable block cipher proposed by Liskov et al. is known.
The Tweakable block cipher has an external parameter called Tweak in addition to a key and a message (that is, a plaintext and a ciphertext). It is known that the Tweakable block cipher in which a message and a Tweak are both n bits can be created with a general n-bit block cipher E such as AES (Advanced Encryption Standard) and an e-AXU hash function H with n-bit input/output (see, for example, NPL 3, NPL 4, and NPL 5).
FIG. 6 is an illustration showing an example of the method of constructing a Tweakable block cipher with an n-bit block and an n-bit Tweak, from an n-bit block cipher E and an n-bit input/output e-AXU hash function H. Specifically, the Tweakable block cipher above can generally be constructed by using the result of applying the Tweak to H as a mask above and below E, as shown in FIG. 6.
The Tweakable block cipher in which a message and a Tweak are both n bits is used, for example, in authentication encryption systems (see PTL 1 and NPL 6), encryption systems for storage (see NPL 7), and online encryption (see NPL 8).
The e-AXU hash function with n-bit input/output can also be used for generating individual IDs using individual variability in physical properties of hardware. For example, NPL 9 states that an e-AXU hash function with 128-bit input/output is constructed with a Toeplitz matrix. NPL 9 also states that the e-AXU hash function has a 64-bit input and a 128-bit output and the matrix is a Toeplitz matrix of order 128.
NPL 10 describes a lemma as to the rank of a matrix with elements in a finite field. NPL 11 describes the conditions of irreducibility of all-one-polynomial.